1. Field of the Invention
The invention relates to the field circuit design and, more particularly, to placing components and routing signals of circuit designs.
2. Description of the Related Art
Circuit designs, and particularly designs for Field Programmable Gate Arrays (FPGA's), have become increasingly complex and heterogeneous. Modern circuit designs can include a variety of different components or resources including, but not limited to, registers, block Random Access Memory (RAM), multipliers, processors, and the like. This increasing complexity makes placement of components as well as the routing of signals within a circuit design more cumbersome.
One component, called a look up table (LUT), is frequently utilized as a basic building block in modern FPGAs. Generally, an LUT is used to implement any of a variety of different functions of 4 inputs. The LUT can be viewed as a sort of single complete multiplexer tree with 4 selector inputs which connected to the LUT through 4 input pins. Traditionally, the input selector pins processed by LUTs had symmetrical delays as modeled in software algorithms. That is, the delays from the input pins of the LUT to the output of the LUT were substantially the same. Thus, there was no substantial difference in choosing either of the 4 input pins for the signals connected to these pins. With regard to modern circuit designs implemented in FPGAs, however, the input selector pins provided to LUTs have become asymmetric in nature in terms of propagation delay. That is, some of the input pins have substantially different propagation delays to the output of the LUT than the remaining input pins.
FIGS. 1A and 1B are schematic diagrams illustrating the asymmetric nature of delays of input pins of a LUT. As shown in FIG. 1A, the LUT 100 includes four physical inputs or pins F1, F2, F3, and F4. Each pin F1, F2, F3, and F4 can receive a signal serving as an input to a function f(F1, F2, F3, F4) implemented by the LUT.
FIG. 1B represents the internal workings of the LUT 100 as a simplistic, complete tree. Pins of the LUT 100 are indicated by arrows. The tree itself includes 4 levels corresponding to the pins F1, F2, F3, and F4. The pins F1, F2, F3, and F4 act as multiplexer select lines. The value received on each respective pin, a 0 or a 1, determines whether a 0 or 1 stored in the memory cells 105 is propagated to a subsequent level of the tree.
The amount of time required for each level of the LUT 100 to produce an output is dependent upon the evaluation time of the previous level in the tree. Thus, level F1 is evaluated before level F2; level F2 is evaluated before level F3, and so on. Level F1, therefore, requires the most time, or is said to have the largest propagation time, for a signal to reach the output of the LUT 100. Conversely, level F4 has the smallest propagation time. This difference in propagation time among the levels of the LUT 100 can be modeled as asymmetric delays in the input pins of the LUT 100.
Conventional circuit placers perform little or no analysis with respect to the arrival time of signals at LUT inputs or the propagation time of various levels of LUTs in a circuit design. As such, a circuit placer may pair an input signal that arrives at the LUT later than the other signals with a pin of the LUT such as F1 that corresponds to a processing path having a high propagation time. In consequence, the processing time required by the LUT is increased. More particularly, the LUT cannot begin processing at level 1 until a signal is received on pin F1. As the signal to pin F1 arrives later than the other input signals to the LUT 100, processing of the LUT 100 is delayed by approximately the difference between the arrival time of the late arriving input signal and earlier arriving signals. Moreover, the pairing of a late arriving signal with a pin having a higher propagation delay further increases the overall time required for the LUT 100 to implement the function f(F1, F2, F3, F4).
What is needed is a technique for analyzing the asymmetry of LUT input pins as well as the time in which signals arrive at those inputs to determine a better pairing of signals with LUT pins.